import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-09-17
 * Time: 10:13
 */
public class test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(3);
        mySingleList.addLast(5);
        mySingleList.show();
    }
    public static void main1(String[] args) {
        System.out.println("(1)=============================");
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(2);
        myLinkedList.addFirst(1);
        myLinkedList.addLast(4);
        myLinkedList.addIndex(2, 3);
        myLinkedList.addIndex(4, 5);
        myLinkedList.display();
        System.out.println(myLinkedList.size());
        System.out.println("(2)=============================");
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addFirst(1);
        myLinkedList1.addFirst(2);
        myLinkedList1.addFirst(1);
        myLinkedList1.addFirst(2);
        myLinkedList1.addFirst(1);
        myLinkedList1.display();
        myLinkedList1.remove(1);
        myLinkedList1.display();
        myLinkedList1.remove(1);
        myLinkedList1.display();
        myLinkedList1.remove(1);
        myLinkedList1.display();
        System.out.println("(3)=============================");
        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addFirst(1);
        myLinkedList2.addFirst(2);
        myLinkedList2.addFirst(1);
        myLinkedList2.addFirst(2);
        myLinkedList2.addFirst(1);
        myLinkedList2.display();
        myLinkedList2.removeAllKey(1);
        myLinkedList2.display();
        System.out.println("(4)=============================");
        myLinkedList1.clear();
        myLinkedList1.display();
        myLinkedList2.clear();
        myLinkedList2.display();
        System.out.println("(5)=============================");

    }
    //7.相同部分
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        int countA = 0;
        int countB = 0;
        MySingleList.ListNode curA = headA;
        MySingleList.ListNode curB = headB;
        while(curA != null){
            countA++;
            curA = curA.next;
        }
        curA = headA;
        while(curB != null){
            countB++;
            curB = curB.next;
        }
        curB = headB;
        int ret = countA - countB;
        if(ret < 0){
            ret = countB- countA;
            curA = headB;
            curB = headA;
        }
        for (int i = 0; i < ret; i++){
            curA = curA.next;
        }
        while (curA != curB){
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
    //4.合并
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode head = newHead;
        while(list1 != null && list2 != null){
            if(list1.value < list2.value){
                newHead.next = list1;
                list1 = list1.next;
            }else{
                newHead.next = list2;
                list2 = list2.next;
            }
            newHead = newHead.next;
        }
        if(list1 == null){
            newHead.next = list2;
        }
        if(list2 == null){
            newHead.next = list1;
        }
        head = head.next;
        return head;
    }

    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        System.out.println("(1)=============================");
//        mySingleList.createList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.show();
        System.out.println("(2)=============================");
        System.out.println(mySingleList.size());
        System.out.println("(3)=============================");
        System.out.println(mySingleList.contains(12));
        System.out.println(mySingleList.contains(67));
        System.out.println("(4)=============================");
        mySingleList.addFirst(99);
        mySingleList.show();
        System.out.println("(5)=============================");
        mySingleList.addIndex(0, 10);
        mySingleList.show();
        System.out.println("(6)=============================");
        mySingleList.removeAllKey(10);
        mySingleList.removeAllKey(100);
        mySingleList.show();
        System.out.println("(7)=============================");
        mySingleList.reverseList();
        mySingleList.show();
        System.out.println("(8)=============================");
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.head = mySingleList.middleNode();
        mySingleList.show();
        mySingleList1.show();
        System.out.println("(9)=============================");
        System.out.println(mySingleList.FindKthToTail(1).value);
        System.out.println("(10)=============================");
        mySingleList.clear();
        mySingleList1.clear();
        mySingleList.show();
        mySingleList1.show();
        System.out.println("(11)=============================");
        mySingleList.addLast(1);
        mySingleList.addLast(3);
        mySingleList.addLast(5);
        mySingleList.addLast(7);
        mySingleList.addLast(9);
        mySingleList1.addLast(2);
        mySingleList1.addLast(4);
        mySingleList1.addLast(6);
        mySingleList1.addLast(8);
        mySingleList1.addLast(10);
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.head = mergeTwoLists(mySingleList1.head, mySingleList.head);
        mySingleList2.show();
        System.out.println("(12)=============================");
        MySingleList mySingleList3 = new MySingleList();
        mySingleList2.reverseList();
        mySingleList3.head = mySingleList2.partition(5);
        mySingleList3.show();
        System.out.println("(13)=============================");
        MySingleList mySingleList4 = new MySingleList();
        mySingleList4.head = mySingleList4.partition(10);
        mySingleList4.show();
        System.out.println("(14)=============================");
        MySingleList mySingleList5 = new MySingleList();
        mySingleList5.addLast(1);
        mySingleList5.addLast(1);
        MySingleList mySingleList6 = new MySingleList();
        mySingleList6.addLast(1);
        mySingleList6.addLast(2);
        mySingleList6.addLast(3);
        mySingleList6.addLast(4);
        mySingleList6.addLast(3);
        mySingleList6.addLast(2);
        mySingleList6.addLast(1);
        MySingleList mySingleList7 = new MySingleList();
        mySingleList7.addLast(1);
        mySingleList7.addLast(2);
        System.out.println(mySingleList5.chkPalindrome());
        System.out.println(mySingleList6.chkPalindrome());
        System.out.println(mySingleList7.chkPalindrome());
        System.out.println("(15)=============================");
        mySingleList.show();
        mySingleList1.show();
        mySingleList2.show();
        mySingleList3.show();
        mySingleList4.show();
        mySingleList5.show();
        mySingleList6.show();
        mySingleList7.show();
        System.out.println("(16)=============================");
        MySingleList mySingleList8 = new MySingleList();
        mySingleList8.head = getIntersectionNode(mySingleList.head,mySingleList1.head);
        mySingleList8.show();
        System.out.println("(17)=============================");
        MySingleList mySingleList9 = new MySingleList();
        mySingleList9.addLast(1);
        mySingleList9.addLast(2);
        mySingleList9.addLast(3);
        mySingleList9.addLast(4);
        mySingleList9.addLast(5);
        mySingleList9.addLast(6);
        mySingleList9.addLast(7);
        mySingleList9.addLast(8);
        MySingleList mySingleList10 = new MySingleList();
        mySingleList10.addLast(1);
        mySingleList10.addLast(3);
        mySingleList10.addLast(5);
        mySingleList10.addLast(8);
        mySingleList9.subList1(mySingleList10.head);
        mySingleList9.show();
        mySingleList10.show();
        mySingleList9.reverse();
        mySingleList9.show();
        System.out.println(mySingleList9.hasCycle());
        System.out.println("(18)=============================");
    }
}
